Preventing execution of malicious code is one of the central problems in computer security. One of the most common defenses to identify and/or filter out unwanted pieces of code is through pattern matching against a large signature base.
Recently a method of attack has been demonstrated, by which an attacker can induce arbitrary behavior in a program whose control flow has been diverted, without injecting any code. In order to accomplish this goal, the attacker executes desired instructions by re-using existing code within the kernel. The pieces of existing code utilized end in return instructions, giving rise to the name ‘return-oriented programming’ for this set of techniques. Although now the program bytes do not constitute code directly, but jump instructions to pieces of code, it may still be possible to create signatures for the most common pointer byte sequences.
In order to understand the origins of return oriented programming consider an adversary who has discovered a code vulnerability in some application and is looking to exploit it. To achieve the exploit, that is, perform desired actions with the victim application's credentials, the attacker has to accomplish two (separate) tasks: First, the attacker has to subvert the program's control flow. Second, the attacker has to redirect the program's execution to point to the desired code. The first task is often completed, for example, by a buffer-overflow attack which overwrites the return address on the stack. The second task is achieved by inserting code (often also on the stack), and making sure the new return address then points to this code.
A common defense against code insertion attacks is the following: memory is either marked writeable or executable, but not both. This feature, dubbed W-xor-X, is supported in current operating systems such as Windows Vista, Mac OS, Linux and OpenBSD.
While effective in many cases against injected code attacks, W-xor-X is ineffective against attacks which do not rely on both writing and executing code. A new class of attacks based on ‘return-oriented-programming’, rely on pointers to natively available code snippets to patch together the desired instructions, instead of having to insert the malicious code first. These attacks are related to, and are generalizations of, the older ‘return-to-libc’ attack.
The ‘return-to-libc’ attack works as follows: the attacker uses for example a buffer overflow to overwrite the return address on the stack with the address of a legitimate instruction which is located in a library such as the libc runtime library on UNIX style systems. The attacker places the arguments to this function in another place on the stack. This attack can circumvent non-executable stack protections.
Return-oriented programming generalizes this concept by using short sequences of assembly instructions that are followed by a return, which are resident in memory. A program is built by chaining together such sequences, which are called ‘gadgets’. Example gadgets compute (AND, XOR, etc.) between two operands. See, for instance, R. Roemer, E. Buchanan, H. Shacham and S. Savage, “Return-Oriented Programming: Systems, Languages, and Applications”, In review, October 2009, or R. Hund, T. Holz, F. C. Freiling, “Return-Oriented Rootkits: Bypassing Kernel Code Integrity Protection Mechanisms”, Proceedings USENIX Security 2009, August 2009, or S. Checkoway, A. Feldman, B. Kantor, J. A. Halderman, E. W. Felten and H. Shacham, “Can DREs Provide Long-Lasting Security? The Case of Return-Oriented Programming and the AVC Advantage”, Proceedings EVT/WOTE 2009, August 2009, which are incorporated herein by reference.
In order to create Return Oriented programs, it is important to have a large collection of candidate instructions or gadgets, i.e. short instruction sequences ending in returns, which are resident in a program's address space. Knowing if a gadget is resident in a program's address space requires (some) knowledge of the target runtime environment. At a minimum, there should be sufficiently varied gadgets to be able to map a given program. It is also preferable to have enough redundancy in the gadget collection to be able to write multiple different return oriented versions of the same agent.
An efficient way of creating a large collection of gadgets is as follows. First, find a sequence of instructions ending in a ‘ret’. Since each valid sequence of instructions ending in ‘ret’ is a gadget, a currently found gadget can be used as a postfix for a potential next gadget, and so build a trie of gadgets. See, for example, Roemer et al.
‘Ret’ instructions can be found by scanning any given base code in the kernel (e.g. including drivers) for the required word(s). For example, for an x86 architecture computer, the opcode for ‘ret’ is 0x09. It is also possible to use a number of alternative formulations of ‘returns’. See, for example, Roemer et al and Hund et al. For x86 architectures, which have a dense variable length instructions set, a large set of ‘ret’ instructions can also be found by the following simple method: start at a given offset at random, and start disassembling until a ‘ret’ is found. Since the disassembly starts at a random offset, it does not have to start at an ‘intended’ instruction boundary. However, since the instruction set for x86 chips is so dense, disassembly of these random words often gives valid instructions. Any ‘ret’ thus found is an ‘unintended’ ‘ret’ instruction. Nevertheless, such unintended ‘ret’ instructions can equally well be used in trie construction. If more ‘gadgets’ need to be found, it is possible to continue the process by simply shifting a byte and repeating the disassembly (a ‘derandomized’ approach) or starting at a different random offset. See, for example, Hund et al. The applicability of a byte shift to generate more unintended returns is somewhat limited by a self-correcting property of Intel binary disassembly: very quickly, disassembly of the shifted sequence leads to the same sequence of instructions as the original sequence. That is, the two sequences differ only in the first few disassembled instructions, see R. Chinchani, E. van den Berg, “A Fast Static Analysis Approach to Detect Exploit Code Inside Network Flows”, Proceedings RAID 2005. As one extreme, it is possible to construct Return Oriented instructions by simply using only the first instruction preceding a found return. This is not very efficient, but does work.
Also, a library of gadgets can equally well be created on RISC-based architectures, e.g. on SPARC machines, but there the instruction set is (short) fixed length, so only intended returns occur.
The basic instructions created above ending in returns, are now patched together to form gadgets for elementary load/store, arithmetic/logic, shift/rotate, and control flow operations. See e.g. Roemer et al and Hund et al.
Having a large collection of instructions and gadgets available, the next step is to build a Mapper. Assume there is already a program available, and it is desired to map/rewrite this program to consist of return oriented instructions/gadgets. One possible method, pursued in e.g. Roemer et al and Hund et al is to write a new, return-oriented compiler, analogous to e.g. a C-compiler, and compile source code with the new return-oriented compiler. This approach is useful when writing new code (as done in exploit generation), or having access to the original source code of a program, provided the new C-compiler is sufficiently rich and complete. For generating code, return oriented shell code is also possible as described in Roemer et al.